// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

// flagalloc在所有生成标志的寄存器之间分配标志寄存器
// 说明书如果需要，将重新计算标志值
// 溢出/恢复。
func flagalloc(f *Func) {
	// 计算我们希望在结束时使用的寄存器内标志值
	// 每个街区。这基本上是一个尽力而为的活变量
	// 分析，所以它可以比完整的分析简单得多。
	end := make([]*Value, f.NumBlocks())
	po := f.postorder()
	for n := 0; n < 2; n++ {
		for _, b := range po {
			// 向后遍历值以找出哪个标志
			// 我们希望在开始时在标志寄存器中的值
			// 在街区的另一边。
			var flag *Value
			for _, c := range b.ControlValues() {
				if c.Type.IsFlags() {
					if flag != nil {
						panic("cannot have multiple controls using flags")
					}
					flag = c
				}
			}
			if flag == nil {
				flag = end[b.ID]
			}
			for j := len(b.Values) - 1; j >= 0; j-- {
				v := b.Values[j]
				if v == flag {
					flag = nil
				}
				if v.clobbersFlags() {
					flag = nil
				}
				for _, a := range v.Args {
					if a.Type.IsFlags() {
						flag = a
					}
				}
			}
			if flag != nil {
				for _, e := range b.Preds {
					p := e.b
					end[p.ID] = flag
				}
			}
		}
	}

	// 对于具有标志控制值的块，这是唯一的值
	// 我们可以在块的末尾保留标志寄存器。（那里
	// 没有放置标志再生指令的位置。）
	for _, b := range f.Blocks {
		if b.Kind == BlockDefer {
			// 延迟块在内部使用/删除标志值。
			end[b.ID] = nil
			continue
		}
		for _, v := range b.ControlValues() {
			if v.Type.IsFlags() && end[b.ID] != v {
				end[b.ID] = nil
			}
		}
	}

	// 计算哪些标志值需要溢出。
	spill := map[ID]bool{}
	for _, b := range f.Blocks {
		var flag *Value
		if len(b.Preds) > 0 {
			flag = end[b.Preds[0].b.ID]
		}
		for _, v := range b.Values {
			for _, a := range v.Args {
				if !a.Type.IsFlags() {
					continue
				}
				if a == flag {
					continue
				}
				// a需要在这里恢复。
				spill[a.ID] = true
				flag = a
			}
			if v.clobbersFlags() {
				flag = nil
			}
			if v.Type.IsFlags() {
				flag = v
			}
		}
		for _, v := range b.ControlValues() {
			if v != flag && v.Type.IsFlags() {
				spill[v.ID] = true
			}
		}
		if v := end[b.ID]; v != nil && v != flag {
			spill[v.ID] = true
		}
	}

	// 在需要的地方添加旗帜溢出和重新计算。
	var remove []*Value // 应检查是否可能删除的值
	var oldSched []*Value
	for _, b := range f.Blocks {
		oldSched = append(oldSched[:0], b.Values...)
		b.Values = b.Values[:0]
		// 当前live标志值（前flagalloc副本）。
		var flag *Value
		if len(b.Preds) > 0 {
			flag = end[b.Preds[0].b.ID]
			// 注：以下情况取决于缺少临界边。
			for _, e := range b.Preds[1:] {
				p := e.b
				if end[p.ID] != flag {
					f.Fatalf("live flag in %s's predecessors not consistent", b)
				}
			}
		}
		for _, v := range oldSched {
			if v.Op == OpPhi && v.Type.IsFlags() {
				f.Fatalf("phi of flags not supported: %s", v.LongString())
			}

			// 如果v将溢出，并且v使用内存，那么我们必须拆分它
			// 进入负载+标志生成器。
			if spill[v.ID] && v.MemoryArg() != nil {
				remove = append(remove, v)
				if !f.Config.splitLoad(v) {
					f.Fatalf("can't split flag generator: %s", v.LongString())
				}
			}

			// 确保v的任何标志arg都在标志寄存器中。
			// 如果没有，请重新计算。
			for i, a := range v.Args {
				if !a.Type.IsFlags() {
					continue
				}
				if a == flag {
					continue
				}
				// 重新计算
				c := copyFlags(a, b)
				// 更新。
				v.SetArg(i, c)
				// 记住最近计算的标志值。
				flag = a
			}
			// 问题五。
			b.Values = append(b.Values, v)
			if v.clobbersFlags() {
				flag = nil
			}
			if v.Type.IsFlags() {
				flag = v
			}
		}
		for i, v := range b.ControlValues() {
			if v != flag && v.Type.IsFlags() {
				// 重新计算控制值。
				remove = append(remove, v)
				c := copyFlags(v, b)
				b.ReplaceControl(i, c)
				flag = v
			}
		}
		if v := end[b.ID]; v != nil && v != flag {
			// 需要重新发布标志生成器以供使用
			// 随后的区块。
			remove = append(remove, v)
			copyFlags(v, b)
			// 注意：此标志生成器未正确连接
			// 使用标志用户。这打破了SSA的代表性。
			// 我们可以用另一个通行证来修复用户，但是现在
			// 我们就不谈了。（Regalloc也有同样的问题
			// 标准regs，然后运行。）
			// 因此，请注意不要添加此标志
			// 将生成器添加到删除列表。
		}
	}

	// 保存实时标志状态以备以后使用。
	for _, b := range f.Blocks {
		b.FlagsLiveAtEnd = end[b.ID] != nil
	}

	// 删除所有现在已失效的值。
	// 要删除的值的数量可能很小，
	// 删除它们需要处理块中的所有值，
	// 所以尽量减少我们接触到的块的数量。

	// 收缩删除以仅包含死值，并删除这些死值。
	for i := 0; i < len(remove); i++ {
		v := remove[i]
		if v.Uses == 0 {
			v.reset(OpInvalid)
			continue
		}
		// 除去。
		last := len(remove) - 1
		remove[i] = remove[last]
		remove[last] = nil
		remove = remove[:last]
		i-- // 在i处重新处理值
	}

	if len(remove) == 0 {
		return
	}

	removeBlocks := f.newSparseSet(f.NumBlocks())
	defer f.retSparseSet(removeBlocks)
	for _, v := range remove {
		removeBlocks.add(v.Block.ID)
	}

	// 处理受影响的块，保留值顺序。
	for _, b := range f.Blocks {
		if !removeBlocks.contains(b.ID) {
			continue
		}
		i := 0
		for j := 0; j < len(b.Values); j++ {
			v := b.Values[j]
			if v.Op == OpInvalid {
				continue
			}
			b.Values[i] = v
			i++
		}
		b.truncateValues(i)
	}
}

func (v *Value) clobbersFlags() bool {
	if opcodeTable[v.Op].clobberFlags {
		return true
	}
	if v.Type.IsTuple() && (v.Type.FieldType(0).IsFlags() || v.Type.FieldType(1).IsFlags()) {
		// 本例处理生成但从未使用标志值的可能性。
		// 在这种情况下，没有相应的选择来覆盖标志值，
		// 因此，我们必须考虑由元组生成指令所覆盖的标志。
		return true
	}
	return false
}

// copyFlags将v（标志生成器）复制到b中，返回副本。
// 如果v的arg也是标志，则递归复制。
func copyFlags(v *Value, b *Block) *Value {
	flagsArgs := make(map[int]*Value)
	for i, a := range v.Args {
		if a.Type.IsFlags() || a.Type.IsTuple() {
			flagsArgs[i] = copyFlags(a, b)
		}
	}
	c := v.copyInto(b)
	for i, a := range flagsArgs {
		c.SetArg(i, a)
	}
	return c
}
